class Solution {
public:
    void dfs(vector<int>& candidates, int index)
    {
        if (sum == _target)
        {
            ret.push_back(path);
            return;
        }
        if (sum > _target)
            return;

        for (int i = index; i < candidates.size(); i++)
        {
            sum += candidates[i];
            path.push_back(candidates[i]);

            dfs(candidates, i);
            sum -= candidates[i];
            path.pop_back();
        }

    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        _target = target;
        dfs(candidates, 0);

        return ret;
    }
private:
    int sum = 0;
    int _target;
    vector<vector<int>> ret;
    vector<int> path;
};